package ex.algorithms.sorting;

import ex.util.CommonUtil;

public class QuickSort {
	public static void sortIncreasing(int[] input) {
		if(input == null || input.length < 2)
			return;
		
		sortIncreasing(input, 0, input.length-1);
		
	}
	
	public static void sortIncreasing(int[] input, int start, int end) {
		if(start >= end)
			return;
		
		int pivot = partition(input, start, end);
		sortIncreasing(input, start, pivot-1);
		sortIncreasing(input, pivot + 1, end);
	}
	
	private static int partition(int[] input, int start, int end) {
		int pivotValue = input[end];
		int i = start-1;
		for(int j=start; j<end; j++) {
			if(input[j] <= pivotValue) {
				i++;
				CommonUtil.swap(input, j, i);
			}
		}
		
		CommonUtil.swap(input, i+1, end);
		return i+1;
	}
}
